

In [ ]:

    
%%HTML
<style>
.container { width:100% }
</style>

A$^*$ Search

The module Set implements sets as AVL trees. The API provided by Set offers the following functions and methods:

Set() creates an empty set.
S.isEmpty() checks whether the set Sis empty.
S.member(x) checks whether x is an element of the set S.
S.insert(x) inserts x into the set S. This does not return a new set but rather modifies the set S.
S.delete(x) deletes x from the set S. This does not return a new set but rather modifies the set S.
S.pop() returns the smallest element of the set S. Furthermore, this element is removed from S.

Since sets are implemented as ordered binary trees, the elements of a set need to be comparable, i.e. if x and y are inserted into a set, then the expression x < y must return a Boolean value and < has to define a linear order. Therefore, sets must not be inhomogeneous, i.e. the sets must not contain elements of different types.

In this notebook, the module Set is used to implement a priority queue that supports the removal of elements.



In [ ]:

    
import Set

The function search takes three arguments to solve a search problem:

start is the start state of the search problem,
goalis the goal state, and
next_states is a function with signature $\texttt{next_states}:Q \rightarrow 2^Q$, where $Q$ is the set of states. For every state $s \in Q$, $\texttt{next_states}(s)$ is the set of states that can be reached from $s$ in one step.
heuristic is a function that takes two states as arguments. It returns an estimate of the length of the shortest path between these states.

If successful, search returns a path from start to goal that is a solution of the search problem $$ \langle Q, \texttt{next_states}, \texttt{start}, \texttt{goal} \rangle. $$ For A$^*$ search to find optimal paths it is required that heuristicis consistent, which requires the following properties:

$\texttt{heuristic}(\texttt{goal}) = 0$.
If $s_2 \in \texttt{next_states}(s_1)$, then we must have $\texttt{heuristic}(s_1) \leq 1 + \texttt{heuristic}(s_2)$.

The function search implements A$^*$ search. It maintains the following variables:

PathDict is a dictionary. For every state s such that PathDict[s] is defined, PathDict[s] is a path from source to s.
Distance is a dictionary. For every state s such that Distance[s] is defined, Distance[s] is the length of the path PathDict[s]. Furthermore, it can be shown that this path is the shortest path connecting source with s. If Distance[s] is defined, then we say that s has been visited.
Estimate is a dictionary. For every state s such that Estimate[s] is defined, Estimate[s] is the expected length of a path from start to goalthat leads via s.
Frontier is an ordered set of pairs of the form $(d, s)$ where $s$ is a state and $d = \texttt{Estimate}[s]$. This set is used as a priority queue.
Explored is the set of all states that have been explored. A state $s$ is explored if all of its neighbours have been visited.



In [ ]:

    
def search(start, goal, next_states, heuristic):
    PathDict = { start: [start] }
    Distance = { start: 0 }           
    estGoal  = heuristic(start, goal)
    Estimate = { start: estGoal }
    Frontier = Set.Set()
    Frontier.insert( (estGoal, start) )
    Explored = set()
    while not Frontier.isEmpty():
        _, state = Frontier.pop()
        if state == goal:
            return PathDict[state]
        stateDist = Distance[state]
        for ns in next_states(state):
            oldEstimate = Estimate.get(ns, None)
            newEstimate = stateDist + 1 + heuristic(ns, goal)
            if oldEstimate == None or newEstimate < oldEstimate:
                Distance[ns] = stateDist + 1
                Estimate[ns] = newEstimate
                PathDict[ns] = PathDict[state] + [ns]
                Frontier.insert( (newEstimate, ns) )
                if oldEstimate != None:
                    Frontier.delete( (oldEstimate, ns) )
        Explored.add(state)

Lets draw the start state and animate the solution that has been found.



In [ ]:

    
%run Sliding-Puzzle.ipynb



In [ ]:

    
%%time
Path = search(start, goal, next_states, manhattan)
print(len(Path)-1)



In [ ]:

    
animation(Path)



In [ ]: